package org.demo.algorithm.leetcode.linked;

import org.demo.algorithm.common.ListNode;

/**
 * 22
 */
public class MergeOrdered {

    public ListNode recursive(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val <= l2.val) {
            l1.next = recursive(l1.next, l2);
            return l1;
        } else {
            l2.next = recursive(l1, l2.next);
            return l2;
        }
    }

    public ListNode iterative(ListNode l1, ListNode l2) {
        ListNode sentry = new ListNode(-1);
        ListNode prev = sentry;
        ListNode l1c = l1;
        ListNode l2c = l2;
        while (l1c != null && l2c != null) {
            if (l1c.val <= l2c.val) {
                prev.next = l1c;
                l1c = l1c.next;
            } else {
                prev.next = l2c;
                l2c = l2c.next;
            }
            prev = prev.next;
        }
        prev.next = l1c == null ? l2c : l1c;
        return sentry.next;
    }

    public static void main(String[] args) {
        MergeOrdered mergeOrdered = new MergeOrdered();
        ListNode iterative = mergeOrdered.iterative(getL1(), getL2());
        while (iterative != null) {
            System.out.println(iterative.val);
            iterative = iterative.next;
        }

        ListNode recursive = mergeOrdered.recursive(getL1(), getL2());
        while (recursive != null) {
            System.out.println(recursive.val);
            recursive = recursive.next;
        }
    }

    public static ListNode getL1() {
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(2);
        ListNode l3 = new ListNode(4);
        l1.next = l2;
        l2.next = l3;
        return l1;
    }

    public static ListNode getL2() {
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(3);
        ListNode l3 = new ListNode(4);
        l1.next = l2;
        l2.next = l3;
        return l1;
    }

}
